Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Practical Applications and Case Studies
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Dynamic Programming Algorithms

In this lesson, we will explore three different approaches to solving dynamic programming problems with more complex examples:

  • Memoization (Top-down approach)
  • Top-down DP with Explicit Recursion
  • Bottom-up DP (Tabulation)

1. Solving a Problem with Memoization

Problem: Calculate the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid. You can only move right or down.

Java
Saved to Cloud

. . . .

Time Complexity for Unique Paths Using Memoization

  1. Recursive Calls:
    • The function findPaths is called recursively to compute the number of unique paths to each cell in the m x n grid.
    • Number of Unique States: Each state is defined by a unique (row, col) combination, and there are such unique states in the grid.
    • Number of Recursive Calls:
      • Each unique state is computed only once, as we use memoization. This prevents redundant recursive calls and ensures each state is solved once.
    • Overall Time Complexity:

Space Complexity for Unique Paths Using Memoization

  1. Memoization Map (memo):

    • The memo map stores results for each unique state (row, col), so it has space complexity .
    • The size of the String keys is insignificant compared to the number of entries, so this does not impact the space complexity significantly.
  2. Recursive Call Stack:

    • Maximum Depth:
      • The maximum depth of the recursive call stack is in the worst case, representing the diagonal traversal of the grid from (m-1, n-1) to (0, 0).
  3. Overall Space Complexity:

    • The total space complexity accounts for both the memoization map and the call stack depth: , for storing results, plus for the recursion stack.

2. Solving a Problem with Top-Down DP

Problem: Calculate the minimum cost to climb a staircase where each step has a certain cost associated with it. You can climb one or two steps at a time.

Java

. . . .

Time Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

  1. Recursive Calls:
    • The function findMinCost is called recursively to compute the minimum cost for each step i.
    • Number of Unique Subproblems:
      • Each index from 0 to n-1 (where n is the length of the cost array) represents a unique subproblem.
      • Since each subproblem is computed only once due to memoization, the total number of recursive calls is .
  2. Key Operations:
    • Base Case Checks:
      • The checks if (i < 0), if (i == 0 || i == 1), and if (dp[i] != -1) run in .
    • Recursive Calculations:
      • For each call to findMinCost, two recursive calls are made (findMinCost(cost, i - 1) and findMinCost(cost, i - 2)), but due to memoization, each index is only processed once.
    • Filling and Returning Values:
      • Storing and returning values in dp[i] take .

Overall Time Complexity:

  • Each index i from 0 to n-1 is processed once, leading to a total time complexity of:

Space Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

  1. DP Array (dp):

    • The dp array is used to store precomputed results for each index from 0 to n-1, taking space.
  2. Recursive Call Stack:

    • Maximum Depth of Recursion:
      • The maximum depth of the recursion is , which occurs when the function is called starting from the highest index down to 0.
    • Space Complexity for Call Stack:

    The space used by the recursion stack can go up to in the worst case.

3. Solving a Problem with Bottom-Up DP

Problem: Find the length of the longest palindromic subsequence in a given string.

Java

. . . .

Time Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

  1. Initialization:

    • Single Character Initialization:
      • The for loop that sets dp[i][i] = 1 for each i runs times, where n is the length of the input string s.
  2. Nested Loops:

    • The outer loop runs times, as it iterates over lengths of substrings starting from 2 up to n.
    • The middle loop runs times for each length, as it starts from the beginning of the string up to n - len.
    • The inner loop computes the value at dp[i][j], where , and runs operations for each combination.
  3. Overall Time Complexity:

    • The number of operations for filling the dp table is because each of the cells in the upper triangle of the 2D array is filled once.
    • Total Time Complexity:

Space Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

  1. DP Table (dp):

    • The 2D dp table has a size of , where n is the length of the input string s.
    • Space used by dp:
  2. Auxiliary Space:

    • The algorithm does not use any additional data structures that grow with the input size.
    • Overall auxiliary space: .

Overall Space Complexity:

  • The total space complexity is:
Graph Algorithms
Coding Interview Problems
Mark as Completed

On this page

  1. Solving a Problem with Memoization

Time Complexity for Unique Paths Using Memoization

Space Complexity for Unique Paths Using Memoization

  1. Solving a Problem with Top-Down DP

Time Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

Space Complexity for Minimum Cost Climbing Stairs Using Top-Down DP

  1. Solving a Problem with Bottom-Up DP

Time Complexity for Longest Palindromic Subsequence Using Bottom-Up DP

Space Complexity for Longest Palindromic Subsequence Using Bottom-Up DP